import java.util.*;


// 注意类名必须为 Main, 不要有任何 package xxx 信息
 class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int v = in.nextInt();
        int[][] arr = new int[n][2];

        for (int i = 0; i < n; i++) {
            arr[i][0] = in.nextInt();  //体积
            arr[i][1] = in.nextInt(); //价值
        }

        System.out.println(dp1(arr, v));
        System.out.println(dp2(arr, v));


    }

    private static int dp1(int[][] arr, int v) {
        int n = arr.length;
        if (n == 1) return arr[0][1];
        int[][] dp = new int[n][v + 1];

        if (arr[0][0] <= v) {
            dp[0][arr[0][0]] = arr[0][1];

            for (int i = arr[0][0] + 1; i < v + 1; i++) {
                dp[0][i] = arr[0][1];
            }

        }




        for (int i = 1; i < n; i++) {
            for (int j = 0; j < v + 1; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j - arr[i][0] >= 0) dp[i][j] = Math.max(arr[i][1] + dp[i - 1][j -
                                arr[i][0]],
                        dp[i][j]);

            }

        }


        return dp[n - 1][v];


    }


    private static int dp2(int[][] arr, int v) {
        int n = arr.length;


        int[][] dp = new int[n][v + 1];
        // if (n == 1) return dp[n - 1][v];

        if (arr[0][0] <= v) dp[0][arr[0][0]] = arr[0][1];

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < v + 1; j++) {

                dp[i][j] = dp[i - 1][j];

                if (j - arr[i][0] > 0 && dp[i - 1][j - arr[i][0]] != 0 ||
                        j - arr[i][0] == 0) dp[i][j]=Math.max(arr[i][1] + dp[i - 1][j -
                                arr[i][0]],
                        dp[i][j]);

            }

        }

        return dp[n - 1][v];

    }
}



class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        int maxNum = 0;
        for (int num : nums) {
            sum += num;
            maxNum=Math.max(maxNum,num);
        }

        if (sum % 2 != 0) return false;
        int k = sum / 2;

        if (maxNum > k) return false;  // 剪枝：最大的数比目标和还大，无法分割
        if (maxNum == k) return true;  // 剪枝：最大的数正好等于目标和

        boolean[] dp = new boolean[k + 1];
        dp[0] = true;  // 初始条件：和为0的子集总是存在

        for (int num : nums) {
            for (int j = k; j >= num; j--) {
                if (dp[j]) continue;  // 剪枝：如果已经可以凑出j，就不用再计算
                dp[j] = dp[j] || dp[j - num];
            }
            if (dp[k]) return true;  // 提前终止：已经找到解
        }

        return dp[k];
    }
}